E. Резервное копирование

Для обеспечения сохранности пользовательских данных Аркадий постоянно изобретает и тестирует новые схемы организации резервного копирования. В этот раз он пронумеровал все имеющиеся у него компьютеры с данными от 1 до n и для каждого компьютера с номером 
от 1 до n−1 назначил резервный компьютер pi. При этом он строго соблюдал правило, что номер компьютера для резервного копирования всегда больше номера самого компьютера, то есть pi>i. По этой причине, у компьютера с номером n компьютера для резервного копирования нет.

В ходе текущего эксперимента Аркадий выбрал некоторую конфигурацию значений pi и будет последовательно отключать компьютеры по одному каждую секунду. Эксперимент заканчивается, когда Аркадий отключает компьютер с номером n. Изначально, на каждом компьютере находится некоторый блок данных размера 1. При отключении компьютера с номером x, изначально расположенный на нём блок данных размера 1 передаётся на компьютер с номером px, при этом, если на компьютере номер x находилось другие блоки данных (полученные от других компьютеров при их отключении), то они исчезают. Если же компьютер px уже отключен, то и блок данных с компьютера x никуда не передаётся и тоже исчезает.
Аркадий хочет, чтобы эксперимент продолжался как можно дольше, но он вынужден соблюдать ещё одно дополнительное ограничение: если на каком-либо компьютере собирается k блоков данных, то в целях сохранности железа этот компьютер необходимо тут же выключить в течение следующей секунды. Обратите внимание, что последняя секунда (во время которой выключается компьютер n) не учитывается.

В первой строке входных данных записано целое число t (1≤t≤20) — количество тестовых примеров.
Далее следует t описаний тестовых примеров, каждое описание начинается со строки содержащей два целых 
числа n и k (1≤n≤100000, 2≤k≤10) — количество компьютеров, участвующих в эксперименте и предельное количество блоков данных на одном компьютере соответственно. 
Вторая строка содержит n−1 число p1,p2,…,pn-1 (i+1≤pi≤n).

Для каждого из t тестовых примеров выведите одно целое число — максимально возможную продолжительность эксперимента, то есть максимальный номер секунды, на которой Аркадий может отключить компьютер с номером n.

